Recently, a color display employing a color lookup table (LUT) system is being widely used. FIG. 12 shows a schematic of the color LUT system. In the figure, if a frame buffer can store all the intensities of the red, green and blue components of image data, the color LUT becomes unnecessary, and it is sufficient to use the data read from the frame buffer as they are as video signals for the color display. However, if it is assumed that each of the red, the green and the blue components is represented by 8 bits, 24 bits are required for one pel of the image data. The frame buffer requires enormous storage, and becomes expensive.
Thus, it is a recent approach to utilize a color LUT, in which the contents of the frame buffer are used as color indexes, the contents of each of the red, the green and the blue components of the color LUT represented by the color indexes are read and utilized as the video signals for the color display.
Therefore, it is sufficient for the pel data in the frame buffer to just accommodate the number of entries of the color LUT. For example, in a case where the number of entries of the color LUT or the number of colors simultaneously displayed on the color display is 256, the pel data of the frame buffer can be represented by 8 bits (1 byte).
At present, there are color LUT-type displays that can simultaneously display 8, 16, 32 or 256 colors. When it is intended to display on such a color display a color image with colors in a number sufficiently higher than the number of colors simultaneously displayable on the display (for example, a color image, each intensity of the red, the green and the blue component of which is represented by 8 bits, has 16.7 million colors), it becomes important to provide a technique that is able to select the optimum number of simultaneously displayed colors, to cause as little deterioration of image quality as possible, and to map the original colors of the color image to those selected colors simultaneously displayable. The technique is called color image quantization.
As described by P. Heckbert in "Color Image Quantization for Frame Buffer Display," ACM SIGGRAPH '82, pp. 297-307, July, 1982, the color quantization technique is roughly divided into uniform sampling and adaptive sampling. The uniform sampling performs quantization by uniformly dividing a color space, and giving a representative color to each divided space. Its advantage lies in the fact that reloading is not necessary once the representative color for each divided space is loaded in a lookup table. Its disadvantage is that the image quality is significantly degraded for an input image whose colors are not uniformly distributed in a color-space, but are locally clustered. Here, the term color-space means various spaces such as RGB space (Red, Green, Blue space), HLS space (Hue, Lightness, Saturation space), CYMB space (Cyan, Yellow, Magenta, Black space) and L*u*v space.
J. Tajima "Uniform Color Scale Applications to Computer Graphics," COMPUTER VISION, GRAPHICS, AND IMAGE PROCESSING, vol. 21, No. 3, pp. 305-325, March, 1983 discloses the uniform sampling in an L*u*v space. The L*u*v space means a color-space which is arranged so that color difference sensed by a human corresponds to a distance in the space, and is also called a uniform color-space.
On the other hand, the adaptive sampling is a technique to change contents of a lookup table according to an input image and to perform quantization to best represent it. We are interested in a color image quantization method according to the adaptive sampling. Various adaptive sampling methods have been proposed. All of them perform quantization in the following four steps. Here we assume that an input image is defined in an RGB space without losing generality.
Step 1: Sample an input image represented by each n bits for each of R, G, and B in a space with each "m" bits for each of R, G, and B (generally m=n), and generate a histogram.
Step 2: Select colors to be loaded in the lookup table ("k" colors) (generally, 2.sup.3m --=k).
Step 3: Perform mapping from the sampled "m" bit RGB space to the lookup table.
Step 4: Assign corresponding color in the lookup table to each pel of the input image.
Among these steps, Step 2 and subsequent steps determine the image quality, but key steps for the quantization itself are Steps 2 and 3. That is, the quality of the quantization depends on Step 2 where the "k" representative colors are selected, and Step 3 where colors "close" to remaining colors are selected from the "k" representative colors, and assigned. In Step 4, the error diffusion method utilizing errors of the quantization or the dither method (random noise method) is also used in many cases.
Known technique for Step 2 is listed in the following. First, P. Heckbert "Color Image Quantization for Frame Buffer Display," ACM SIGGRAPH, July, 1982 discloses the popularity algorithm and the median cut algorithm. The former is a method that sorts the histogram in a descending order of frequency, and selects "k" colors from the top as the representative colors. This method is simple, but has a noticeable disadvantage that the image quality significantly deteriorates if many colors are distributed with the equal frequency.
On the other hand, the latter is a method that calculates the maximum and the minimum values in each direction of R, G, and B components, and splits the space with their median value recursively. Extra time is necessary to find the maximum and the minimum values in each direction of R, G, and B components, and, if the median values are given in real numbers, much processing time is required because of real number calculation. If they are given in integers, it has a disadvantage that errors may be caused whether they are truncated or rounded.
Y. Tozawa discloses the population equalization algorithm in the U.S. Pat. No. 4,654,720. It is a method that selects "k" representative colors while finding neighborhood spaces which render the frequency of the "k" colors becomes as equal as possible in the color-space. This method provides excellent image quality, but has a disadvantage in that much time is necessary to merge the neighborhood spaces depending on the input image, and that enormous work areas (storage) are required.
S. Iwai and S. Uno disclose the fixed area +chromaticity based algorithm in the U.S. Pat. No. 4,710,806. It is a method in which a fixed area is provided in a color lookup table in advance, entries whose values appear in the fixed area are removed from the histogram before a histogram is generated based on the ratio between R, G, and B (chromaticity), and representative colors are found according to peak values appearing therein. It features the fact that colors in a region with constant chromaticity and varying lightness are mainly selected by utilizing the characteristic of the human eye that is sensitive to the lightness. Existence or nonexistence of the fixed area depends on an input image, so that it may be an advantage or a disadvantage. However, it has a disadvantage in that it requires much processing time because real number calculation is involved in a series of processes such as generation of the histogram for brightness and detection of the peaks (particularly, calculation of angles such as arc cosine).
On the other hand, as for Step 3, it is necessary to find neighborhood representative color for those remaining colors with more than one entry in the histogram. Y. Tozawa's technique processes them through merge while incrementing the distance as 1-st neighborhood, 2-nd neighborhood, and so on. Other approaches are arranged to find representative colors in neighborhood by introducing some measure of distance (for example, Euclidean distance in the RGB space). The distance calculation for finding the neighborhood is a time-consuming process.
According to the present invention means are provided for processing both Steps 2 and 3 in the adaptive sampling method at a high speed. The processing time and the storage required for quantization by this means are only proportional to the number of colors simultaneously displayable on the color display, and are not affected by the number of colors and the distribution of colors specific to the original image. It can work even on a personal computer because less storage is required for implementing the means.
The method and apparatus for color image quantization according to the invention execute the following steps to select "k" display colors from the 2.sup..epsilon.ni colors obtained by assigning n.sub.i bits for representing the intensity level of each of "a" kinds of basic color 1.ltoreq.i.ltoreq.a), and to quantize an original color image comprising a number of pels for which any one of the said 2.sup..epsilon.ni colors may be assigned so that it may be displayed with the said "k" display colors:
(a) Inputting the said original image, sampling it in a color-space defined by assigning m.sub.i (m.sub.i .ltoreq.n.sub.i) bits for representing intensity level of each of the said "a" kinds of basic color, and generating an a-dimension histogram,
(b) Repeating dividing a color-space into X child-spaces, when calculating a space-occupying number by:
calculating the number of pels assigned for colors within each generated child-space, referring to the said histogram, PA0 and multiplying the calculation result by a weighing-factor corresponding to a level of the division,
(c) Preparing a tree-structured list which describes a parent-child relationship of color-spaces, and updating the list by registering a newly generated color space each time a color space is divided,
(d) Selecting "k" color spaces as representative color spaces in the descending order of the space-occupying number, among those located at ends of the tree-structured list,
(e) Selecting a representative color for each of the said "k" representative color-spaces, and providing the representative color with an index,
(f) For a color other than the representative color within each of the said "k" representative color-spaces, giving the index assigned for the representative color of the color-space, for a color within a color-space other than the said representative color-spaces in the said tree-structured list, finding a representative color-space located close to the color-space, and giving it the index assigned for the found representative color-space, and
(g) For each pel in the said original image, obtaining an index given to the color assigned for the pel, and storing it in storage device.
The above-mentioned "a" kinds of basic color are typically those basic colors such as red, green and blue. However, the scope of the invention is not limited to an image consisting of only color components. For example, in the field of remote sensing, a component such as ground surface temperature may be included in the basic component. In this regard, an image to be quantized according to the invention can be called a multi-dimensional multi-value image in a precise manner. However, in the following, the term "color image" is used for convenience.